{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "2d229699",
   "metadata": {},
   "source": [
    "# 给定一个字符串，求它的最长回文字串的长度"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "1bede322",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\t1\t2\t3\t4\t5\t6\t7\t8\t9\t10\t11\t12\t13\t14\t15\t16\t17\t18\t19\t20\t\n",
      "2\t3\t1\t4\t5\t4\t2\t3\t4\t5\t5\t6\ta\ts\td\tf\td\ts\ta\td\tf\t\n",
      "center : 15 max : 7\n"
     ]
    }
   ],
   "source": [
    "// 中心拓展法\n",
    "#include <iostream>\n",
    "#include <tuple>\n",
    "#include <cstring>\n",
    "std::tuple<int, int> LongestPaildrone(const char *s, int n){\n",
    "    int i,j,max,c,pos;\n",
    "    if(s == 0 || n < 1){\n",
    "        return std::make_tuple(0, 0);\n",
    "    }\n",
    "    max = 0;\n",
    "    // i 为回文的中心位置\n",
    "    for(i = 0; i < n; i++){\n",
    "        //回文长度为奇数\n",
    "        for(j = 0; (i - j >= 0) && (i + j < n); ++j){\n",
    "            if(s[i - j] != s[i + j]){\n",
    "                break;\n",
    "            }\n",
    "            c = j * 2 + 1;\n",
    "        }\n",
    "        if(c > max){\n",
    "            max = c;\n",
    "            pos = i;\n",
    "        }\n",
    "        //回文为偶数位\n",
    "        for(j = 0; (i - j >= 0) && (i + j + 1 < n); ++j){\n",
    "            if(s[i - j] != s[i + j + 1]){\n",
    "                break;\n",
    "            }\n",
    "            c = j * 2 + 2;\n",
    "        }\n",
    "        if(c > max){\n",
    "            max = c;\n",
    "            pos = i;\n",
    "        }\n",
    "    }\n",
    "    for(int i = 0; i < n; i++){\n",
    "        std::cout <<i<<\"\\t\";\n",
    "    }\n",
    "    std::cout << std::endl;\n",
    "    for(int i = 0; i < n; i++){\n",
    "        std::cout <<s[i]<<\"\\t\";\n",
    "    }\n",
    "    std::cout << std::endl;\n",
    "    return std::make_tuple(pos, max);\n",
    "}\n",
    "const char* str = \"231454234556asdfdsadf\";\n",
    "//auto [pos, max] = LongestPaildrone(str, strlen(str)); //C++17\n",
    "auto t = LongestPaildrone(str, strlen(str));\n",
    "std::cout <<\"center : \"<<std::get<0>(t)<<\" max : \"<<std::get<1>(t)<< std::endl;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "1c6c7b44-e6c7-4d18-aed6-33e0a83703c9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\t1\t2\t3\t4\t5\t6\t7\t8\t9\t10\t11\t12\t13\t14\t15\t16\t17\t18\t19\t20\t21\t22\t23\t24\t25\t26\t27\t28\t29\t30\t31\t32\t33\t34\t35\t36\t37\t38\t39\t40\t41\t42\t\n",
      "#\t2\t#\t3\t#\t1\t#\t4\t#\t5\t#\t4\t#\t2\t#\t3\t#\t4\t#\t5\t#\t5\t#\t6\t#\ta\t#\ts\t#\td\t#\tf\t#\td\t#\ts\t#\ta\t#\td\t#\tf\t#\t\n",
      "center : 29 max : 7\n"
     ]
    }
   ],
   "source": [
    "//Manacher算法\n",
    "#include <iostream>\n",
    "#include <memory>\n",
    "#include <tuple>\n",
    "#include <algorithm>\n",
    "#include <string>\n",
    "std::tuple<int, int> LongestPaildrone(const char *s, int n) {\n",
    "    int p_len = 2 * n + 1;\n",
    "    char ss [p_len];\n",
    "    for(int i = 0; i < p_len; i++){\n",
    "        if(i % 2 == 0){\n",
    "            ss[i] = '#';\n",
    "        }else{\n",
    "            ss[i] = s[(i - 1) / 2];\n",
    "        }\n",
    "    }\n",
    "    int p[p_len];\n",
    "    p[0] = 1;\n",
    "    int i;\n",
    "    int mx = 0;\n",
    "    int id = 0;\n",
    "    int sum = 0;\n",
    "    for(i = 1; i < p_len; i++){\n",
    "        if(mx > i){\n",
    "            p[i] = std::min(p[2 * id - 1], mx - i);\n",
    "        }else{\n",
    "            p[i] = 1;\n",
    "        }\n",
    "        while(ss[i - p[i] - 1] == ss[i + p[i] + 1]){\n",
    "            p[i] ++;\n",
    "        }\n",
    "        if (p[i] + i > mx){\n",
    "            mx = p[i] + i;\n",
    "            id = i;\n",
    "            sum = std::max(sum, p[i]);\n",
    "        }\n",
    "    }\n",
    "    for(int i = 0; i < p_len; i++){\n",
    "        std::cout <<i<<\"\\t\";\n",
    "    }\n",
    "    std::cout << std::endl;\n",
    "    for(int i = 0; i < p_len; i++){\n",
    "        std::cout <<ss[i]<<\"\\t\";\n",
    "    }\n",
    "    std::cout << std::endl;\n",
    "    return std::make_tuple(id - (2 * sum - 1), sum);\n",
    "}\n",
    "\n",
    "const char* str = \"231454234556asdfdsadf\";\n",
    "auto t = LongestPaildrone(str, strlen(str));\n",
    "std::cout <<\"center : \"<<std::get<0>(t)<<\" max : \"<<std::get<1>(t)<< std::endl;"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++14",
   "language": "C++14",
   "name": "xcpp14"
  },
  "language_info": {
   "codemirror_mode": "text/x-c++src",
   "file_extension": ".cpp",
   "mimetype": "text/x-c++src",
   "name": "c++",
   "version": "14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
